package com.cdy.demo.algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Leetcode198 {



	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;
		TreeNode(int x) { val = x; }
	}

	// f(o)f(o) 表示选择 oo 节点的情况下，oo 节点的子树上被选择的节点的最大权值和；
	// g(o)g(o) 表示不选择 oo 节点的情况下，oo 节点的子树上被选择的节点的最大权值和；ll 和 rr 代表 oo 的左右孩子。
	Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
	Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

	/**
	 * 337
	 * @param root
	 * @return
	 */
	public int rob3(TreeNode root) {
		dfs(root);
		return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
	}

	public void dfs(TreeNode node) {
		if (node == null) {
			return;
		}
		dfs(node.left);
		dfs(node.right);
		//打劫当前节点， 左右子节点就不能打劫了
		f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
		// 不打劫当前节点， 取左边最大和右边的最大
		g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0))
				+ Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
	}

	/**
	 * 198
	 * @param nums
	 * @return
	 */
	public int rob2(int[] nums) {
		int[] dp = new int[nums.length+2];

		for (int i = nums.length - 1; i >= 0; i--) {
			dp[i] = Math.max(dp[i + 1], nums[i] + dp[i + 2]);

		}
		return dp[0];
	}

	/**
	 * 213
	 * @param nums
	 * @return
	 */
	public int rob(int[] nums) {

		if (nums.length == 0) {
			return 0;
		}
		if (nums.length == 1) {
			return nums[0];
		}

		int[] num1 = Arrays.copyOfRange(nums,0, nums.length-1);
		int[] num2 = Arrays.copyOfRange(nums, 1,nums.length);
		int[] num3 = Arrays.copyOfRange(nums, 1,nums.length-1);
		return Math.max(rob2(num1), Math.max(rob2(num2), rob2(num3)));
	}

	class Entry  {
		boolean rob;
		int offset;
		int total;

		public Entry(boolean rob,int offset, int total) {
			this.rob = rob;
			this.offset = offset;
			this.total = total;
		}

		@Override
		public int hashCode() {
			return offset + total;
		}

		@Override
		public boolean equals(Object obj) {
			if (obj instanceof Entry) {
				return ((Entry) obj).rob == this.rob && ((Entry) obj).offset == this.offset && ((Entry) obj).total==this.total;
			} else {
				return false;
			}
		}
	}

	HashMap<Entry, Integer> map = new HashMap<>();

	/**
	 * 198
	 * @param nums
	 * @return
	 */
	public int rob1(int[] nums) {
		if (nums.length == 0) {
			return 0;
		}
		if (nums.length == 1) {
			return nums[0];
		}
		return Math.max(dfs(nums, true, 0, 0),
				dfs(nums, false, 0, 0));

	}


	private int dfs(int[] num,boolean rob, int offset, int sum) {
		Integer integer = map.get(new Entry(rob,offset, sum));
		if (integer != null) {
			return integer;
		}
		if (offset == num.length - 1) {
			if (rob) {
				return sum;
			} else {
				return sum + num[offset];
			}
		}
		int dfs = dfs(num, false, offset + 1, sum);
		if (rob) {
			map.put(new Entry(rob,offset, sum), dfs);
			return dfs;
		}else {
			int max = Math.max(dfs(num, true, offset + 1, sum + num[offset]), dfs);
			map.put(new Entry(rob, offset, sum), max);
			return max;
		}

	}
}
